package package1;
//求解背包问题
public class beibao {
	public static void main(String[] args) {
		int m =10; //背包容量
		int n =3; //物品种类
		int weight[]= {3,4,5}; //物品重量
		int value[]= {4,5,6};   //物品价值
		int dp[][] =test(m,n,weight,value); //背包里的价值
		//输出背包价值表格
		System.out.println("输出背包价值表格");
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++) {
				System.out.print("\t"+dp[i][j]);
				if(j==m)
					System.out.println();
			}
		//容量为m的背包能够装入物品的最大价值
		int maxvalue =dp[n][m];
		System.out.println("背包可以存储的最大价值"+maxvalue);
		System.out.println("背包可以存储的最大价值2:"+test00(m,n,weight,value));
	}
//背包问题求解
	private static int[][] test(int m, int n, int[] weight, int[] value) {
		//dp[i][m]表示前i件物品恰好放入一个容量为m的背包可以获得的最大价值
		int dp[][]=new int[n+1][m+1]; 
		for(int i=0;i<n+1;i++)
			dp[i][0]=0;  //初始化，表示有i件物品放入容量为0的背包，价值为0
		for(int j=0;j<m+1;j++)
			dp[0][j]=0;  //初始化，表示没有物品放入的背包价值也为0
		for(int i=1;i<n+1;i++)
			for(int j=1;j<m+1;j++) {
//当背包里的物品为i件重量为j时，如果第i件的重量为weight【i-1】小于重量j时，dp【i】【j】有下列两种情况
//(1)物品i不放入背包，所以dp[i][j]为dp[i-1][j]的值
//(2)物品i放入背包，则背包剩余重量为j-weight[i-1]，所以从dp[i][j]为dp[i-1][j-weight[i-1]]的值加上当前物品i的值				
				
				if(weight[i-1]<=j) {
					if(dp[i-1][j]<dp[i-1][j-weight[i-1]]+value[i-1])
						dp[i][j]=dp[i-1][j-weight[i-1]]+value[i-1];
					else
						dp[i][j] =dp[i-1][j];
				}else
					dp[i][j] =dp[i-1][j];
			}		
		
		return dp;
	}
//背包问题求解优化
	private static int test00(int m,int n,int[]weight,int[]value){
		int[] dp=new int[m+1];
		//逆序实现
		for(int i=1;i<n+1;i++) 			
			for(int j=m;j>=weight[i-1];j--){
			dp[j] =Math.max(dp[j-weight[i-1]]+value[i-1],dp[j]);
		}
		return dp[m];
		
	}

}
